package ListNode;

public class d230715 {

    // 一、链表相加(二)
    public ListNode addInList (ListNode head1, ListNode head2) {
        // 反转链表
        // 反转后，可以从个位数开始加，个、十、白...
        head1 = reverse(head1);
        head2 = reverse(head2);
        // 创建一个存放结果的链表
        ListNode result = new ListNode(-1);
        ListNode cur = result;
        // 存放进位
        int carry = 0;

        while (head1 != null || head2 != null || carry == 1) {
            // 统计当前位置上的值
            // head1.val + head2.val + carry
            int val = carry;
            if (head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            if (head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            if (val > 9) {
                carry = 1;
                val -= 10;
            } else {
                carry = 0;
            }
            cur.next = new ListNode(val);
            cur = cur.next;
        }
        // 反转链表
        return reverse(result.next);
    }
    public static ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }


    // 二、单链表的排序
    // 归并排序
    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            // 递归到只有一个元素时, 就是有序的, 可以进行合并了
            return head;
        }
        // 快慢指针找到链表中间位置 mid
        // left 记录 mid 前一个位置，用来断开链表
        ListNode left = head;
        ListNode mid = head;
        ListNode right = head;
        while (right != null && right.next != null) {
            left = mid;
            mid = mid.next;
            right = right.next.next;
        }
        // 将链表断开
        left.next = null;
        // 递归
        ListNode leftNode = sortInList(head);
        ListNode rightNode = sortInList(mid);
        return merge(leftNode, rightNode);
    }
    // 合并两个有序链表
    private static ListNode merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode cur = head;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }

        if (list1 == null) {
            cur.next = list2;
        } else {
            cur.next = list1;
        }

        return head.next;
    }

    // 三、判断一个链表是否为回文结构
    public boolean isPail (ListNode head) {
        // 统计链表长度
        ListNode cur1 = head;
        int length = 0;
        while (cur1 != null) {
            length++;
            cur1 = cur1.next;
        }
        int mid = length / 2;
        if (length % 2 != 0) {
            mid += 1;
        }
        // 将 cur2 移到链表中间
        ListNode cur2 = head;
        for (int i = 0; i < mid; i++) {
            cur2 =  cur2.next;
        }
        // 将链表后半部分反转
        cur2 = reverse(cur2);
        cur1 = head;
        // 对比
        while (cur2 != null) {
            if (cur1.val != cur2.val) {
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }

    // 链表奇偶重排
    public ListNode oddEvenList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode evenHead = head.next;  // 记录第一个偶数位节点
        ListNode odd = head;            // 遍历奇数位节点
        ListNode even = evenHead;       // 遍历偶数位节点
        while (even != null && even.next != null) {
            // 偶数位的下一个是奇数位
            odd.next = even.next;
            odd = odd.next;
            // 奇数位的下一个是偶数位
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}
